#include "BTreeNode.h"

using namespace std;

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{
	RC rc;
	if ( pid < 0 )
	{
		return RC_INVALID_PID;
	}
	if ( rc = pf.read( pid, (void *) buffer ) )
	{
		return rc;
	}
	return 0; 
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{ 
	RC rc;
	if ( pid < 0 )
	{
		return RC_INVALID_PID;
	}
	if ( rc = pf.write( pid, (void *) buffer) )
	{
		return rc;
	}
	return 0;
}

/*
 * Returns the max number of entries per node.
 * @return the max number of entries per node.
 */
const unsigned int BTLeafNode::maxNodeSize()
{
	//Available space for entries divided by the size of each entry.
	int resSpace = (2 * sizeof(int)) + (2 * sizeof(PageId));
	int entSize = sizeof(RecordId) + sizeof(int);
	int totSpace = PageFile::PAGE_SIZE;
	
	int rem = (totSpace - resSpace)/entSize;
	return rem - (rem%2);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{ 
	return *ptr_keyCount; 
}

/*
 * Returns the value of the root page Id
 */
PageId BTLeafNode::getRoot()
{
	return *ptr_rootPageId;
}

/*
 * Returns the tree height
 */
int BTLeafNode::getHeight()
{
	return *ptr_treeHeight;
}

RC BTLeafNode::setTreeHeight(int height)
{
	if ( height < 0 )
	{
		return RC_INVALID_ATTRIBUTE;
	}
	*ptr_treeHeight = height;
	return 0;
}

/*
 * Set this node's keycount
 * @param newCount[in] the new number of keys in this node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setKeyCount(int newCount)
{
	if ( newCount < 0 )
	{
		return RC_INVALID_ATTRIBUTE;
	}
	else
	{
	*ptr_keyCount = newCount;
	return 0;
	}
}

/*
* Set the root page id.
* @param rootPid[IN] the new root pid
* @return 0 if successful
*/

RC BTLeafNode::setRoot(PageId rootPid)
{
	*ptr_rootPageId = rootPid;
	return 0;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{ 
	//Check for errors
	RC rc;
	if ( getKeyCount() >= maxNodeSize() )
	{
		return RC_NODE_FULL;
	}
	if ( rid.sid < 0 || rid.pid < 0 )
	{
		return RC_INVALID_RID;
	}
	
	//Find location to insert and key node sorted.
	int insertPos;
	if (rc = locate(key, insertPos) )
	{
		return rc;
	}
	
	
	//Starting at the last entry, move each entry until the insert spot back
	RecordId tmpR;
	int tmpK;
	for ( int curEnt = getKeyCount(); curEnt != insertPos; curEnt-- )
	{
		if ( rc = readEntry(curEnt - 1, tmpK, tmpR) )
		{
			return rc;
		}
		if ( rc = writeEntry(curEnt, tmpK, tmpR) )
		{
			return rc;
		}
	}
	
	//Finally insert the entry in it's position
	if ( rc = writeEntry( insertPos, key, rid ) )
	{
		return rc;
	}
	
	//Increment the keyCount
	setKeyCount(getKeyCount() + 1);
	return 0; 
	
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{ 
	//Check for errors
	RC rc;
	if ( rid.sid < 0 || rid.pid < 0 )
	{
		return RC_INVALID_RID;
	}
	if ( sibling.getKeyCount() != 0 )
	{
		return RC_INVALID_CURSOR;
	}
	if ( getKeyCount() != maxNodeSize() )
	{
		return RC_INVALID_CURSOR;
	}
	
	//Copy the second half of the entries to sibling
	RecordId tmpR;
	int tmpK;
	int halfPoint = getKeyCount()/2;
	int sentCnt = 0;
	for (int i = halfPoint; i < maxNodeSize(); i++)
	{
		if ( rc = readEntry(i, tmpK, tmpR) )
		{
			return rc;
		}
		if ( rc = sibling.insert(tmpK, tmpR) )
		{
			return rc;
		}
		sentCnt++;
	}
	
	//Update key counts for each node
	sibling.setKeyCount( sentCnt );
	setKeyCount( halfPoint );
	
	//set siblingKey output
	if ( rc = readEntry(0, siblingKey, tmpR) )
	{
		return rc;
	}
	
	//Insert the new entry to the correct node.
	if ( key < siblingKey )
	{
		if ( rc = insert(key, rid) )
		{
			return rc;
		}
	}
	else
	{
		if ( rc = sibling.insert(key, rid) )
		{
			return rc;
		}
	}
	
	return 0; 
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{ 
	//Linear search for entry with key >= searchKey
	RC rc;
	int tmpkey;
	RecordId rid;

	for(eid = 0; eid != getKeyCount(); eid++)
	{
		if( rc = readEntry(eid, tmpkey, rid) )
		{
			return rc;
		}
		if(tmpkey >= searchKey)
		{
			break;
		}
	}

	return 0;
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{

	if ( eid >= getKeyCount() )
	{
		return RC_INVALID_CURSOR;
	}
	int *keyptr;
	PageId *pid;
	int *sid;

	int keySpot = 12+12*eid;
	keyptr = (int*)(buffer+keySpot);
	key = *keyptr;
	
	int pidSpot = 4+12*eid;
	pid = (PageId*)(buffer+pidSpot);
	rid.pid = *pid;
	
	int sidSpot = 8+12*eid;
	sid = (int*)(buffer+sidSpot);
	rid.sid = *sid;

	return 0;
	
}

/*
 * Write a (key, rid) pair to the eid input.
 * @param eid[IN] the entry position to write to,
 * @param key[IN] the key to write
 * @param rid[IN] the recordid to write
 */
 
RC BTLeafNode::writeEntry(const int eid, const int key, const RecordId rid)

{
	if ( eid >= maxNodeSize() )
	{
		return RC_INVALID_CURSOR;
	}
	if ( rid.pid < 0 || rid.sid < 0 )
	{
		return RC_INVALID_RID;
	}

	int *keyptr;
	PageId *pid;
	int *sid;
	
	
	int keySpot = 12+12*eid;
	keyptr = (int*)(buffer+keySpot);
	*keyptr = key;
	

	int pidSpot = 4+12*eid;
	pid = (PageId*)(buffer+pidSpot);
	*pid = rid.pid;

	
	int sidSpot = 8+12*eid;
	sid = (int*)(buffer+sidSpot);
	*sid = rid.sid;

	return 0;
	
}


/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */

PageId BTLeafNode::getNextNodePtr()
{
  PageId *nextNode;
  
  int spot = PageFile::PAGE_SIZE - 4;

  nextNode = (PageId*)(buffer+spot);
  
  return *nextNode;
}
/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
 

RC BTLeafNode::setNextNodePtr(PageId pid)
{
  RC rc;
  
  if( pid < 0 )
  {
	return RC_INVALID_PID;
  }

  PageId *nextNode;
  int spot = PageFile::PAGE_SIZE - 4;

  nextNode = (PageId*)(buffer+spot);
  *nextNode = pid;

  return 0;
}


RC BTLeafNode::CopyOverBuffer(char oldBuffer[])
{
	memcpy(buffer, oldBuffer, 1024);
	return 0;
}

/*
 * Returns the max number of entries per node.
 * @return the max number of entries per node.
 *
const unsigned int BTLeafNode::maxNodeSize()
{
	int MaxNumbKeys = ((PageFile::PAGE_SIZE-4)/8)-1;
	
	return MaxNumbKeys;
}
 *
 * Was the second definition of the same function, would cause debug errors.
 * Left code here incase your implementation depends on it later, in which case we
 * might have a lot to resolve 
 */
 
 
/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
BTNonLeafNode::BTNonLeafNode()
{ 
	// If PAGE_SIZE = 1024, the max keys should be 127.
    maxKeys = ((PageFile::PAGE_SIZE-4)/8)-1;
  
}



RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{ 
	if(!pf.read(pid,buffer))
		return 0;
	else
		return RC_FILE_READ_FAILED;
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{ 
	if(!pf.write(pid,buffer))
		return 0;
	else
		return RC_FILE_WRITE_FAILED;
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{ 
	int NumbOfKeys;
	memcpy(&NumbOfKeys, buffer, 4);
	return NumbOfKeys;
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{ 
	//          PageID || KEY || PageID || KEY
	// MEMORY :    4      8      12        16
	// all of type Int. sizeof(int) = 4;
	if (getKeyCount() >= maxKeys)
		return RC_NODE_FULL;

	int TotalMemoryBytes = 8+(getKeyCount()*8);
	int TemporaryPID; // Create a temp pid to move over PIDS
	int TempKey; // Create a temp key to move over keys

	char TempBuffer[PageFile::PAGE_SIZE]; // Create a temp buffer to move data over
	int CurrentPageID;
	int LoopIter=0; // This keeps track of how many times the for loop is run

	int NumbBytes; // This is used in the for loop to keep track of the number of Bytes stored
		
	memcpy(&TempKey, buffer, 4);
	TempKey++;
	memcpy(buffer, &TempKey, 4);


	for(int k=8; k<TotalMemoryBytes; k+=8)
	{
		memcpy(&CurrentPageID, buffer+k, 4);

		if(key <= CurrentPageID)
		{
			// Move over all data to the right 8 bytes
			NumbBytes = (getKeyCount()-LoopIter)*8;

			memcpy(TempBuffer, buffer+k, NumbBytes);
			memcpy(buffer+k+4, &pid, 4);
			memcpy(buffer+k, &key, 4);
			memcpy(buffer+k+8, TempBuffer, NumbBytes);
			return 0;
		}
		LoopIter++;
	}
	
	// If no spot is available, append data to back.. at buffer + TotalMemoryBytes

	memcpy(buffer+TotalMemoryBytes, &key, 4);
	memcpy(buffer+TotalMemoryBytes+4, &pid, 4);
	return 0; 
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 
	void * memcpy ( void * destination, const void * source, size_t num );
	Copy block of memory
	Copies the values of num bytes from the location pointed by source directly to the memory block pointed by destination.

 
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{ 
	

	int TotalByteSize = 8+(getKeyCount()*8); // k
	int HalfByteSize = (((getKeyCount()/2))*8)+8;  // i
	int NewByteLoc = ((8+(getKeyCount()*8))-HalfByteSize)-4;  // j

	int TempKey1;
	int TempKey2;

	char TempBuff1[1024];
	char TempBuff2[1024];

	insert(key,pid);

	// Copy over to temp buffers

	memcpy(TempBuff1, buffer, HalfByteSize); // Copy into TempBuff1, first half
	memcpy(TempBuff2+4, buffer+HalfByteSize+4, NewByteLoc); 
	memcpy(&midKey, buffer+HalfByteSize, 4);  // Find the middle Key

	TempKey1 = getKeyCount()/2;
	TempKey2 = (getKeyCount() - getKeyCount()/2)-1;

	memcpy(TempBuff1, &TempKey1, 4);
	memcpy(TempBuff2, &TempKey2, 4);
	

	memcpy(sibling.buffer, TempBuff1, TotalByteSize);
	sibling.CopyOverBuffer(TempBuff2);
	
	return 0; 
}



/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{ 
	int TotalSize = (getKeyCount()*8)+4; // getKeyCount()*8+4
	int ChildKey;
	for(int j = 8; j<TotalSize; j+=8) {  // Either < or <=, same as below, check again

		memcpy(&ChildKey, buffer+j, 4);

		if(searchKey < ChildKey)
		{
			memcpy(&pid, buffer+j-4, 4);
			return 0;
		}
	}

	memcpy(&pid, buffer+TotalSize, 4);	
	return 0; 
}


/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error. */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{ 
	int initialSize = 1; // Assume the initial Size is 1 key.
	// Order:  Size, pid1, key, pid2 
	memcpy(buffer, &initialSize, 4);
	memcpy(buffer+4, &pid1, 4);
	memcpy(buffer+8, &key, 4);
	memcpy(buffer+12, &pid2, 4);
	
	return 0; 

}


RC BTNonLeafNode::CopyOverBuffer(char oldBuffer[])
{
	memcpy(buffer, oldBuffer, 1024);
	return 0;
}
